\documentclass[paper=a4, fontsize=11pt]{scrartcl}
\newcommand{\bfvec}[1]{\mbox{\boldmath$#1$}}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{calligra,inslrmin,chancery,charter}
\usepackage[top=0.75in, bottom=1in, left=0.5in, right=0.5in]{geometry} 
\usepackage{amsmath,amssymb}
\title{	
\normalfont \normalsize 
\textsc{Shanghai Jiaotong University, Zhiyuan College} \\ [25pt]
\huge Homework 6 \\
}
\author{Feng Shi}
\date{\normalsize\today}
\begin{document}
\maketitle
\begin{enumerate}
\item[Ex 3.32]
{\Large Solution:}

Denote a 3-CNF formula of $n$ variables and $m$ 3-clauses $F_3(n,m)$.\\
And define a monotone (increasing) property of $F_3(n,m)$ by\\

\textbf{Definition of Increasing Property.}
\textsl{\bfvec{Q} is an increasing property of $F_3(n,m)$ 
if any 3-CNF formula obtain by adding \textbf{clauses} to $F_3(n,m)$ also has
property \bfvec{Q}}\\

\textbf{Lemma 1.} Let \bfvec{Q} be an increasing property of $F_3(n,m)$. Then
$$\forall 0\leq m_1\leq m_2<\infty, \ Prob\big( F_3(n,m_q) \ has \ \bfvec{Q} \big)
	\leq Prob\big( F_3(n,m_2) \ has \ \bfvec{Q} \big)$$
\textbf{Proof:} (of \textsl{lemma 1})\\
First generate $F_3(n,m_1)$, then generate $F_3(n,m_2-m_1)$. Take the union
of two formulas to get $F_3(n,m_2)$. Then if $F_3(n,m_1)$ has property \bfvec{Q}
$F_3(n,m_3)$ must also has property \bfvec{Q}.\\

\textbf{Definition of m-fold replication of $F_3(n,m)$.}
\textsl{Let $F_3(n,m')$ be a $m-$fold replication of $F_3(n,m)$. First make $m$
copies of $F_3(n,m)$, with clauses generated independently, and include every clause
present in any of the $m$ copies in to $F_3(n.m')$.}\\

\textbf{Theorem:}\textsl{Every increasing property \bfvec{Q} of $F_3(n,m)$ has a
threshold $m_{1/2}$ where $m_{1/2}$ is the $m$ such that}
$$Prob\big( F_3(n,m) \ has \ \bfvec{Q} \big)=\frac{1}{2}$$
\textbf{Proof:} (of theorem)\\
Let $F_3(n,m(n))$ be any 3-CNF formula.
\begin{enumerate}
\item[i.]
Let $m_0(n)$ be any function such that $\lim_{n\to\infty}\frac{m_0(n)}{m(n)}=0$. Need
to prove:\\
\textbf{Statement 1.}$$Prob\big( F_3(n,m_0(n)) \ has \ \bfvec{Q}\big)\to 0 \ as \ n\to\infty$$
Proof by contradiction: assume $Prob\big( F_3(n,m_0(n)) \ has \ \bfvec{Q}\big)$ does
not converge to $0$ as $n\to\infty$, then by the definition of limitation, 
$$\exists \varepsilon>0 \ \forall N\in\mathbb{N} \ \exists n>N \ 
Prob\big( F_3(n,m_0(n)) \ has \ \bfvec{Q}\big)>\varepsilon$$
Take there infinitly many $n$ the set $I$.\\
Take $d=\lceil \frac{1}{\varepsilon} \rceil$, and Let $F_3(n,m'(n))$ be a $d-$fold
replication of $F_3(n,m_0(n))$. Similar proof to the textbook yields
$$Prob\big( F_3(n,m'(n)) \ does \ not \ have \ \bfvec{Q} \big)
	\leq \big(Prob\big( F_3(n,m_0(n)) \ does \ not \ have \ \bfvec{Q} \big)\big)^d$$
$$m'(n)=1-(1-m_0(n))^d\leq 1-(1-dm_0(n))=dm_0(n)$$
$$Prob\big( F_3(n,m'(n)) \ has \ \bfvec{Q}\big)
	\leq Prob\big( F_3(n,dm_0(n) \ has \ \bfvec{Q})\big)$$
$$Prob\big( F_3(n,dm_0(n) \ does \ not \ have \ \bfvec{Q})\big)
	\leq Prob\big( F_3(n,m'(n)) \ does \ not \ have \ \bfvec{Q}\big)$$
$$Prob\big( F_3(n,dm_0(m)) \ does \ not \ have \ \bfvec{Q}\big)
	\leq \big(Prob\big( F_3(n,m'(n)) \ does \ not \ have \ \bfvec{Q}\big)\big)^d$$
So
$$Prob\big( F_3(n,m'(n)) \ does \ not \ have \ \bfvec{Q}\big)
\leq (1-\varepsilon)^d\\
\leq \frac{1}{e}\leq \frac{1}{2}$$
Then by increasing property of \bfvec{Q}, $dm_0(n)\geq m(n)$ for infinitely many $n$
in the set $I$ which contradicts with the condition that 
$\lim_{n\to\infty}\frac{m_0(n)}{m(n)}=0$. So \textsl{statement 1} is proved.
\item[ii.]
Let $m_0(n)$ be and function such that $\lim_{n\to\infty}\frac{m_0(n)}{m(n)}=\infty$.
Need to prove:\\
\textbf{Statement 2.}$$Prob\big( F_3(n,m_0(n)) \ has \ \bfvec{Q}\big)\to 1 \ as
\ n\to\infty$$
This can be done by a symmetric argument.
\end{enumerate} % end of proof

\vspace{20pt}
\item[Ex 4.8]
\begin{enumerate}
\item[-]{\Large Solution 1:}\\
First prove $$PQ^T=\sum_{i}p_iq_i^T$$
Let $A=PQ^T$ and $B=\sum_{i}p_iq_i^T$. Then 
$$a_{ij}=\sum_{k=1}^{r}p_{ik}q_{jk}$$
and
\begin{align*}
b_{ij}&=\sum_{k=1}^{r}\lbrace p_kq_k^T\rbrace _{ij}\\
	&=\sum_{k=1}^{r}p_{ik}q_{jk}\\
	&=a_{ij}
\end{align*}
So $$PQ^T=\sum_{i}p_iq_i^T$$
\vspace{20pt}
Then we prove $\sum_{i=1}^{r}\sigma _{i}u_{i}v_{i}^T=UDV^T$\\
Let $B=\sum_{i=1}^{r}\sigma _{i}u_{i}v_{i}^T$, and $A=UDV^T$.\\
Then $$a_{ij}=\sum_{k=1}^{r}\sigma _{ik}u_{kk}v_{jk}$$
and
\begin{align*}
b_{ij}&=\sum_{k=1}^{r}\lbrace \sigma _{k}u_{k}v_{k}^T \rbrace _{ij}\\
		&=\sum_{k=1}^{r}\sigma _{ik}u_{kk}v_{jk}\\
		&=a_{ij}
\end{align*}
So $\sum_{i=1}^{r}\sigma _{i}u_{i}v_{i}^T=UDV^T$.\\
\item[-] {\Large Solution 2:}\\
Straight forward by block matrix multiplication.
\begin{align*}
UDV^T&=
\left(
\begin{array}{cccc}
 u_1 & u_2 & \cdots & u_r
\end{array}
\right)
\left(
\begin{array}{cccc}
 \sigma_1 & & & \\
 & \sigma_2 & & \\
 & & \ddots & \\
 & & & \sigma_r
\end{array}
\right)
\left(
\begin{array}{c}
v_1^T \\
v_2^T \\
\vdots \\
v_r^T
\end{array}
\right)
\\
&=
\left(
\begin{array}{cccc}
 \sigma_1 u_1 & \sigma_2 u_2 & \cdots & \sigma_r u_r
\end{array}
\right)
\left(
\begin{array}{c}
v_1^T \\
v_2^T \\
\vdots \\
v_r^T
\end{array}
\right)
\\
&
=
\sum_{i=1}^r \sigma_i u_i v_i^T
\end{align*}

\end{enumerate} % end of 4.8
\end{enumerate} % end of questions
\end{document}

